README.md

53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. 

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solutions (Rust)

1. Brute Force

implSolution{pubfnmax_sub_array(nums:Vec<i32>) -> i32{letmut max = nums[0];for i in0..nums.len(){letmut sum = 0;for j in i..nums.len(){ sum += nums[j];if sum > max { max = sum;}}} max }}

2. One Pass

implSolution{pubfnmax_sub_array(nums:Vec<i32>) -> i32{letmut sum = 0;letmut max_sum = std::i32::MIN;letmut min_sum = 0;for n in nums { min_sum = min_sum.min(sum); sum += n; max_sum = max_sum.max(sum - min_sum);} max_sum }}